#define _CRT_SECURE_NO_WARNINGS

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int>answer(temperatures.size(), 0);
        stack<pair<int, int>>s;
        s.push(make_pair(temperatures[answer.size() - 1], answer.size() - 1));
        for (int i = answer.size() - 2; i >= 0; i--)
        {
            while (s.size() != 0 && temperatures[i] >= s.top().first)
                s.pop();
            if (s.size() == 0)
                answer[i] = 0;
            else
                answer[i] = s.top().second - i;
            s.push(make_pair(temperatures[i], i));
        }
        return answer;
    }
};

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int>answer(temperatures.size(), 0);
        stack<int>s;
        s.push(answer.size() - 1);
        for (int i = answer.size() - 2; i >= 0; i--)
        {
            while (s.size() != 0 && temperatures[i] >= temperatures[s.top()])
                s.pop();
            if (s.size() != 0)
                answer[i] = s.top() - i;
            s.push(i);
        }
        return answer;
    }
};

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int>answer(temperatures.size(), 0);
        stack<int>s;
        for (int i = 0; i < answer.size(); i++)
        {
            while (s.size() != 0 && temperatures[i] > temperatures[s.top()])
            {
                answer[s.top()] = i - s.top();
                s.pop();
            }
            s.push(i);
        }
        return answer;
    }
};

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& nums2) {
        vector<int>answer(nums2.size(), -1);
        stack<int>s;
        for (int i = 0; i < answer.size(); i++)
        {
            while (s.size() != 0 && nums2[i] > nums2[s.top()])
            {
                answer[s.top()] = i;
                s.pop();
            }
            s.push(i);
        }
        return answer;
    }

    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        vector<int>answer = dailyTemperatures(nums2);
        vector<int>ret(nums1.size(), 0);
        unordered_map<int, int>m;
        for (int i = 0; i < nums2.size(); i++)
        {
            m[nums2[i]] = answer[i];
        }
        for (int i = 0; i < nums1.size(); i++)
        {
            if (m.find(nums1[i])->second == -1)
                ret[i] = -1;
            else
            {
                ret[i] = nums2[m.find(nums1[i])->second];
            }
        }
        return ret;
    }
};